#include "Segment.h"
#include "LKH.h"
#include "Sequence.h"

static GainType BestG2;

static int MinLxRec(int k, GainType G0, GainType currentCostToX, int currentDiffToX);
static int CompareToB(int id1,int id2,int id3,int id4);

float SearchMinLx()
{
	Node *t1,*t2;
	int X2;
	GainType G0;

    GainType Gain, Cost;
    int i, it = 0;
    Candidate *Nt1;
    Segment *S;
    SSegment *SS;

    Reversed = 0;
    S = FirstSegment;
    i = 0;
    do {
        S->Size = 0;
        S->Rank = ++i;
        S->Reversed = 0;
        S->First = S->Last = 0;
    }
    while ((S = S->Suc) != FirstSegment);
    SS = FirstSSegment;
    i = 0;
    do {
        SS->Size = 0;
        SS->Rank = ++i;
        SS->Reversed = 0;
        SS->First = SS->Last = 0;
    }
    while ((SS = SS->Suc) != FirstSSegment);

    FirstActive = LastActive = 0;
    Swaps = 0;

    /* Compute the cost of the initial tour, Cost.
       Compute the corresponding hash value, Hash.
       Initialize the segment list.
       Make all nodes "active" (so that they can be used as t1). */
    Cost = 0;
    Hash = 0;
    i = 0;
    t1 = FirstNode;
    do {
        t2 = t1->OldSuc = t1->Suc;
        t1->OldPred = t1->Pred;
        t1->Rank = ++i;
        Cost += (t1->SucCost = t2->PredCost = C(t1, t2)) - t1->Pi - t2->Pi;
        Hash ^= Rand[t1->Id] * Rand[t2->Id];
        t1->Cost = INT_MAX;
        for (Nt1 = t1->CandidateSet; (t2 = Nt1->To); Nt1++)
            if (t2 != t1->Pred && t2 != t1->Suc && Nt1->Cost < t1->Cost)
                t1->Cost = Nt1->Cost;
        t1->Parent = S;
        S->Size++;
        if (S->Size == 1)
            S->First = t1;
        S->Last = t1;
        if (SS->Size == 0)
            SS->First = S;
        S->Parent = SS;
        SS->Last = S;
        if (S->Size == GroupSize) {
            S = S->Suc;
            SS->Size++;
            if (SS->Size == SGroupSize)
                SS = SS->Suc;
        }
        t1->OldPredExcluded = t1->OldSucExcluded = 0;
        t1->Next = 0;
        if (KickType == 0 || Kicks == 0 ||
            !InBestTour(t1, t1->Pred) || !InBestTour(t1, t1->Suc))
            Activate(t1);
    }
    while ((t1 = t1->Suc) != FirstNode);
    if (S->Size < GroupSize)
        SS->Size++;
    Cost /= Precision;
    PredSucCostAvailable = 1;



	MinLx = INT_MAX;

	K = Swaps == 0 ? MoveType : SubsequentMoveType;
	
    /* Choose t2 as one of t1's two neighbors on the tour */
    for (X2 = 1; X2 <= 2; X2++) {
		t2 = X2 == 1 ? PRED(t1) : SUC(t1);
		if (FixedOrCommon(t1, t2) ||(RestrictedSearch && Near(t1, t2) &&
           (Trial == 1 || (Trial > BackboneTrials && (KickType == 0 || Kicks == 0)))))
           continue;
        G0 = C(t1, t2);

		t[1] = t1;
		t[2] = t2;
		T[2 * K] = 0;
		BestG2 = MINUS_INFINITY;

		MarkDeleted(t1, t2);

        MinLxRec(2, G0, 0, 0);
		UnmarkDeleted(t1, t2);
	}
	if((MinLx > 0)&&(MinLx != INT_MAX))
		return MinLx;

	return 0;
}

static int MinLxRec(int k, GainType G0, GainType currentCostToX, int currentDiffToX)
{
    Candidate *Nt2;
    Node *t1, *t2, *t3, *t4;
    GainType G1, G2, G3, Gain;
    int X4, i;
    int Breadth2 = 0;
	float lx;

    t1 = t[1];
    t2 = t[i = 2 * k - 2];
    if (Swaps == 0 && GainCriterionUsed && G0 <= t2->Cost)
        return 0;
    incl[incl[i] = i + 1] = i;
    incl[incl[1] = i + 2] = 1;
    /* Choose (t2,t3) as a candidate edge emanating from t2 */
    for (Nt2 = t2->CandidateSet; (t3 = Nt2->To); Nt2++) {
        if (t3 == t2->Pred || t3 == t2->Suc ||
            ((G1 = G0 - Nt2->Cost) <= 0 && GainCriterionUsed &&
             ProblemType != HCP && ProblemType != HPP)
            || Added(t2, t3))
            continue;
        if (++Breadth2 > MaxBreadth)
            break;
        MarkAdded(t2, t3);
        t[2 * k - 1] = t3;
        G[k] = G1 + t3->Pi;
        /* Choose t4 as one of t3's two neighbors on the tour */
        for (X4 = 1; X4 <= 2; X4++) {
            t4 = X4 == 1 ? PRED(t3) : SUC(t3);
            if (FixedOrCommon(t3, t4) || Deleted(t3, t4))
                continue;
            t[2 * k] = t4;
            G2 = G1 + C(t3, t4);
			G3 = G2 - C(t4, t1);
			currentCostToX += G3 / Precision;
			currentDiffToX += CompareToB(t1->Id,t2->Id,t3->Id,t4->Id);
            if (t4 != t1 && !Forbidden(t4, t1) && (!c || G2 - c(t4, t1) > 0))
			{
   //             G3 = G2 - C(t4, t1);
				if(currentDiffToX < 0)
				{
					lx = currentCostToX / currentDiffToX;
					if( (lx < MinLx)&&(lx > 0) )
					{
						MinLx = lx;
						return 1;
					}
				}
            }
            if (Backtracking && !Excludable(t3, t4))
                continue;
            MarkDeleted(t3, t4);
            if (k < K) {
                if (MinLxRec(k + 1, G2,currentCostToX, currentDiffToX)) {
                    UnmarkAdded(t2, t3);
                    UnmarkDeleted(t3, t4);
                    return 1;
                }
                incl[incl[1] = 2 * k] = 1;
            }
            UnmarkDeleted(t3, t4);
        }
        UnmarkAdded(t2, t3);
        if (t3 == t1)
            continue;
        incl[1] = 2 * k;
        incl[2 * k - 2] = 2 * k - 1;
    }
    return 0;
}

static int CompareToB(int id1,int id2,int id3,int id4)
{
	int dis=0;
	
    if((BetterArray[id1][0]==id2)||BetterArray[id1][1]==id2)
		dis++;
	if((BetterArray[id3][0]==id4)||BetterArray[id3][1]==id4)
		dis++;
	if((BetterArray[id1][0]==id4)||BetterArray[id1][1]==id4)
		dis--;
	if((BetterArray[id3][0]==id2)||BetterArray[id3][1]==id2)
		dis--;

	return dis;
}